1. Field of the Invention
The present invention relates to a circuit configuration for generating random numbers, and relates in particular the layout of the circuit for a random number generator on an integrated circuit.
The generation of random numbers is of great importance for many areas of science and technology. Thus, random numbers are required for numerous applications in statistics as well as for cryptographic purposes. It is precisely cryptography that is increasingly gaining in importance in the course of the propagation of data networks and the associated security problems. Therefore, the automatic generation of random numbers constitutes an important area in electrical engineering and electronics, especially in data processing. Not only the generation of random numbers but also the quality thereof is important. Not all methods can generate random numbers which are equally xe2x80x9crandomxe2x80x9d. Rather, it is usually possible, precisely when analyzing a large number of random numbers which have been generated by a specific random number generator, to identify patterns which lead to a deviation from the ideal, random distribution of the generated numbers. A measure of the quality of random numbers is their entropy, as described by Shannon-in xe2x80x9cA Mathematical Theory of Communicationxe2x80x9d, The Bell System Technical Journal, vol. 27, p. 379 (1948).
A method of generating random numbers which is known in the prior art is done by sampling a signal having a high frequency with a second signal having a significantly lower frequency. These signals are thus voltages which are present at specific outputs and oscillate back and forth between two amplitude values and do this at a specific rate in the temporal profile. The sampling is effected in a special circuit into which both signals are fed. In this case, a specific point in the wave profile of the second signal is always used in order to determine an instant at which the first signal is sampled, that is to say the value of the signal (for example measured as voltage) is ascertained and converted into a numerical value.
In digital circuits, these are in the simplest case the values zero or one, for example as xe2x80x9conexe2x80x9d if, at the sampling instant, the wave course of the first signal is situated above the mean value (for example 0 volts), and as xe2x80x9czeroxe2x80x9d if the wave course is situated below the mean value. However, it is equally possible to make continuous interpretation of the value obtained in order thus to obtain an analog number (for example a voltage in millivolts which is converted 1:1 as number).
In the case of ideal wave courses of the two signals, it would be possible to observe a periodicity in the sampling of the amplitude values, which results from the ratio of the two frequencies. Consequently, it would not be possible to generate genuine random numbers with the aid of such a random number generator. In practice, however, the waves of the two signals are not ideal wave courses, rather, precisely in the microelectronic field, an inaccuracy is generated in the wave course due to an unavoidable noise. This can have the effect that a well functioning random number generator could be achieved with as few as two simple predetermined frequencies, if the signals were independent of one another.
In practice, however, such a simple random number generator does not satisfy the high requirements made of the quality of the random number to be generated. This is because it is of essential importance for the quality of the random numbers that the two signals are independent of one another. This means that one signal does not lead to influencing of the other signal through electrical signal paths situated in the circuit used, so that the two signals are coupled to one another in a specific manner.
In so-called physical noise generators which correspond to the above principle, an attempt is made to solve this problem of the-independence of the two signals for example-by virtue of the signal to be sampled, that is to say the first signal, having a non-constant frequency. Such a signal to be sampled can be obtained for example by integrating into the circuit for generating the random numbers a so-called voltage-coupled oscillator (voltage controlled oscillator, VCO) whose control input is fed by a periodically varying signal, as is provided by a second oscillator, for example. As a result, this has the effect that the frequency of the signal of the VCO is modulated in a manner dependent on the wave course of the second oscillator. In this case, the second oscillator may also be a VCO which is operated with a constant voltage for example at its control input, so that an oscillation signal having a constant frequency is output at its signal output. However, this approach, too, has still not led to satisfactory results for all areas of use. As a result, it can happen that the two signals are temporarily coupled, so that a mixed frequency is formed provided that the frequency of the first signal is suitable for such coupling at a specific point in time and the two signals diverge from one another again after a specific time. As a result, the quality of the random numbers provided by the circuit fluctuates with the varying frequency of the first signal. Consequently, there is still a need for random number generators in which the quality of the random numbers generated is better.
German Patent No. DD 279 763 A1 describes a method for generating random numbers in microcomputers, in which two non-correlated electrical oscillations are utilized whose frequencies differ at least by the factor 100. The oscillations are generated by two independent sources, to be precise in such a way that there is correlation neither between the frequencies nor between the phase angles of the two oscillations. The oscillations of the higher frequency are counted by a counter started by a microcomputer, and the oscillation of the lower frequency is utilized to stop the counter. The random number is then available, after the stopping of the counter, as counter reading for further processing.
U.S. Pat. No. 5,859,450 describes a guard ring which is provided for reducing the dark current of a photodiode. What is involved in this case is an annular highly doped region in semiconductor material, which, according to the description in column 4 of U.S. Pat. No. 5,859,540, changes the position of the depletion zone and thus reduces the dark current. A guard ring is generally a doped region in semiconductor material which surrounds a component for the purpose of current delimitation.
It is accordingly an object of the invention to provide a random number generator which overcomes the above-mentioned disadvantages of the heretofore-known random number generators of this general type and which provides an improved independence of the two signals.
With the foregoing and other objects in view there is provided, in accordance with the invention, a circuit configuration, including:
an integrated circuit;
a random number generator configuration provided on the integrated circuit;
the random number generator configuration including a first clock generator circuit for generating a first signal having one of a first frequency and a first frequency range with a first mean value, and the random number generator configuration including a second clock generator circuit for generating a second signal having one of a second frequency and a second frequency range with a second mean value, the first and second clock generator circuits generating the first and second signals such that one of the second frequency and the second mean value is smaller than one of the first frequency and the first mean value;
the first clock generator circuit having a first voltage supply, the second clock generator circuit having a second voltage supply;
the random number generator configuration including a generator configured to sample the first signal with the second signal and configured to generate at least one random number in dependence of a sampling result; and
the random number generator configuration having at least one isolation measure selected from the group consisting of the first and second generator circuits being spaced apart from one another by a maximum spacing distance on the integrated circuit, the first and second voltage supplies being isolated from one another, and at least one guard ring being placed around each of the first and second clock generator circuits.
The present invention is based on the principle of providing a series of measures which, individually or in combination, can decisively improve the independence of the two signals of the random number generator.
In other words, the invention is therefore generally directed at a random number generator on an integrated circuit having a first clock generator circuit having a first voltage supply for generating a first signal of a first frequency or of a first frequency range, a second clock generator circuit having a second voltage supply for generating a second signal of a second frequency and of a second frequency range, which or whose mean value is lower than the first frequency, and a generator, in which the first signal can be sampled by the second signal and which can generate at least one random number in a manner dependent on the result of the sampling, characterized in that the clock generator circuits are disposed as far away from one another as possible on the integrated circuit and/or the two voltage supplies are isolated from one another and/or at least one guard ring is placed around each of the clock generator circuits.
The first clock generator circuit, which supplies the signal to be sampled, can thus either generate a fixed frequency or output a variable frequency which varies in a predetermined frequency range. The simplest case of a fixed frequency has already been described above as prior art and is based on the principle that random numbers can nevertheless be generated as a result of unavoidable noise within the components. The use of a complete frequency range, that is to say the outputting of a signal having a variable frequency as such, is current state of the art.
The same applies to the second clock generator circuit. While the latter is usually of fixed frequency, it may equally be possible also to configure the second signal of variable frequency with a specific frequency range. In this case, the number of random numbers generated per unit time can fluctuate with the frequency of the second signal. However, this configuration may have the advantage of improving the quality of the random numbers.
As outlined above, the generator generates random numbers through evaluation of the temporal profiles and values of the two signals. In the simplest case, the generator may be a flip-flop into whose input the first signal is fed and whose output is always connected up to a new value when, for example, the second signal present at a control input has a rising edge. Corresponding realizations of such a circuit are familiar to the person skilled in the art.
Separating the two clock generator circuits on the integrated circuit by the maximum possible distance has the effect that the influence of the two signals on one another decreases with distance. Depending on the size of the entire integrated circuit, it is thereby possible to obtain a result of varying quality. In this case, xe2x80x9cas far away from one another as possiblexe2x80x9d or xe2x80x9cmaximum spacing distancexe2x80x9d is to be understood to mean that the components which form the two clock generator circuits, taking account of other circuitry conditions of the integrated circuit, lie at an extremely large distance from one another, for example in diagonally opposite corners of the integrated circuit.
Isolating the voltage supplies in accordance with the invention has the effect that the signal cannot bring about a crosstalk behavior onto the electric currents of the voltage supply, which represents a customary path for the coupling of the frequencies of the two signals.
Finally, guard rings likewise help to prevent the propagation of the signals via the integrated circuit.
In particular, it is preferred for two or even all three of the measures proposed to be realized simultaneously in a random number generator on an integrated circuit according to the present invention. All of the measures contribute to improving the independence of the signals.
The voltage supplies may preferably be isolated through the use of at least one RC element. RC elements are assemblies which allow only signals in a specific narrow frequency range to pass through and block other frequencies. Consequently, it is possible to select an RC element which can impede the other signal, which, after all, has a different frequency, effectively at the entry into the respective other clock generator circuit. It is also possible to dimension the RC element such that it prevents the exit of the signal from the clock generator circuit. If the output frequency is a variable frequency, it is appropriate to select the RC element such that the mean value of the frequencies present is transmitted. While it may be sufficient to use an RC element which filters one of the voltage supplies, preferably an RC element may in each case be provided for each of the clock generator circuits, and isolates the latter.
As an alternative or in addition to the use of RC elements, it may also be possible for the voltage supplies to be isolated through the use of at least one voltage regulator. In this case, then, both clock generator circuits may firstly be supplied by a common voltage supply, but the latter is passed via a respective voltage regulator which, due to its configuration, likewise enables separation of the signals.
The invention may be characterized in that the first signal has a variable frequency, or in that the second signal has a variable frequency. As already explained above, this relates to the possibility of allowing the frequency to change periodically by using corresponding components.
As already stated in-the explanation of the prior art, it is advantageous that the frequency of the second signal is significantly lower than the frequency of the first signal. In particular, it is preferred for the second signal to have a frequency which is at-least ten times lower than the frequency of the first signal, particularly preferably at least one hundred times lower than the frequency of the first signal.
The selection of the frequencies makes it possible to obtain a so-called jitter (variation of the temporal occurrence of a specific signal state) for the second signal, which covers a plurality of oscillations of the first signal, so that more random sampling of the first signal is possible.
The generator generates at least one random number. However, since the clock generator circuits supply a continuous signal, it is appropriate and preferred for the generator to generate a sequence of random numbers. In actual fact, quite generally a stream of random numbers is generated which, depending on the reaching of a specific region in the wave course of the second signal, in each case supplies a number, or a digit of a number. By way of example, it is possible to configure the generator such that it generates binary numbers including zeros and ones, and to combine in each case a predetermined number of these binary values to form an overall random number. Thus, it is possible, for example, to combine 16 or 32 binary numbers to form a suitable random number of 16 or 32 bits.
As already explained, the generator can include merely a flip-flop in a simple embodiment. However, this can have the effect, despite the measures according to the invention, that the generator provides a non-constant power during the random number generation, e.g. owing to the non-constant frequency of the second signal. Furthermore, the random number may be influenced toward a specific value, that is to say have an inherent weighting. It is therefore preferred for the generator furthermore to have an equalizing circuit for the compensation of a non-constant power and/or a weighting in the random number generation. If the second signal, which samples the first signal, also has a floating profile (i.e. a frequency that changes periodically between a minimum and a maximum value), then the power of the random number generator also changes with frequency. This can be compensated for by a preferred equalizing circuit which can be realized for example by a feedback shift register to which the output signals of the random number generator are fed. As is known, a shift register is an entropy storage. If signals, for example bits, are taken from the shift register at a constant rate which is less than or equal to the minimum output signal rate of the random number generator, then the signal stream taken (for example a bit stream) has an entropy which is greater than or equal to the entropy of the signal stream from the random number generator. However, other post-processing methods on circuits are also conceivable which serve to improve the quality of the random numbers generated.
In further preferred embodiments, the first and/or the second clock generator circuit may have at least one voltage-coupled oscillator and a further oscillator, whose signal output is connected to a control input of the voltage-coupled oscillator. This configuration, which is known in principle, although not in combination with the invention, enables a further improvement of the quality of the random numbers. The further oscillator may also be a voltage-coupled oscillator whose control input is connected to a constant voltage. In this way, the voltage-coupled oscillator acts like a simple oscillator which outputs only one frequency. When a voltage-coupled oscillator is used, the circuit can be simplified overall, since fewer different components or assemblies are required.
In order to further improve the quality of the random numbers generated, it may likewise be preferred for the first and/or the second clock generator circuit to have a plurality of series-connected voltage-coupled oscillators, the signal output of each of the voltage-coupled oscillators except for the last of the series being connected to the control input of the next voltage-coupled-oscillator. In this way, it is possible to obtain an even more complex frequency pattern in the first signal output, so that the periodicity of the sampling with the second signal increases further.
Other features which are considered as characteristic for the invention are set forth in the appended claims.
Although the invention is illustrated and described herein as embodied in a random number generator, it is nevertheless not intended to be limited to the details shown, since various modifications and structural changes may be made therein without departing from the spirit of the invention and within the scope and range of equivalents of the claims.
The construction and method of operation of the invention, however, together with additional objects and advantages thereof will be best understood from the following description of specific embodiments when read in connection with the accompanying drawings.